A reliable communications network can be constructed using unreliable nodes and unreliable links. With the appropriate use of redundant network resources, network reliability can be maintained in the face of link and node failures. This redundancy implies some inefficiency in the utilization of network capacity and/or delays in restoring the network to its full transport capability following a failure. There is a tradeoff between utilization efficiency on the one hand, and restoration delays and complexity on the other.
One example of a communication network is a telephone network. In current telephone networks, most subscribers are connected to network nodes, in the form of central offices (COs), by dedicated twisted pair access lines. Typically, a CO and its attached subscribers are arranged in a star topology. However, some subscribers are connected to COs via access rings. Usually, the COs are interconnected by links in the form of fiber optic transmission lines physically forming a mesh topology. Currently, logical connections among COs are established along interlocking rings superimposed on the physical mesh topology of the fiber plant.
A “ring” configuration provides the simplest and most straightforward way to protect against failures so that the network capability can be restored following a failure. In particular, Synchronous Optical Network (SONET) rings have been widely accepted as basis for reliable network design. With this approach, a relatively small number of nodes are interconnected via a ring topology so that between any two nodes (i.e., an “ingress” node and a “egress” node) on the rings, data can flow in two directions around the ring, clockwise and counterclockwise. These two directions represent physically diverse paths so that failures along these paths tend to be independent. Typically, the working (primary) data flow is over a working path in one direction around the ring, while the associated protection (backup) data flow is over a protection path in the opposite direction. For SONET rings, certain bytes of the SONET overhead are used to notify the nodes along the ring when a failure occurs. Based on the indicated failure, source data can be switched to the protection path at its ingress node and protection data can be switched to its destination at the egress node.
Transmission lines, which are deployed in environments that cannot be physically protected, are vulnerable to failures, particularly fiber cuts. SONET rings have been employed very effectively to provide fast restoration following fiber cuts and other types of line failures. In many cases, SONET rings can detect failures and restore service quickly, so that class 4 and class 5 voice switches will not drop calls. It is relatively easy to implement ring-type restoration within SONET equipment without the need to signal network elements outside the ring.
Most COs are end offices (or wire centers), which terminate subscriber access lines. Some COs are limited to interoffice switching. In a network, the average number of access lines per CO is more than 10000, with more access lines per CO in densely populated urban areas and fewer in sparsely populated rural areas.
Since most COs were built to serve local customers, the geographic distribution of COs is driven by the population distribution. Historically, each community (population cluster) had one or more COs, with a single CO in most towns and multiple COs in cities. COs tend to be unevenly distributed in two-dimensional space. However, in moderately populated suburban areas, the distribution is fairly even. Transmission lines interconnecting the COs usually follow the roads or railways, and the distribution of communications traffic tends to be similar to the distribution of transportation traffic.
Local access transport areas (LATAs) are areas that delineate the flow of communication traffic within the United States. Inter-LATA traffic is restricted by government regulations. Within a LATA, traffic is normally handled by a local exchange carrier (LEC), while traffic crossing LATA boundaries is usually handed off to an inter-exchange carrier (IXC). LATA boundaries are seams that impede the free flow of traffic. It is anticipated that in the next several years, the restrictions on inter-LATA services will gradually be lifted, so that the seams within networks may be eliminated.
In most cases, COs are physically interconnected by fiber optic cables containing multiple fibers. Each fiber may contain multiple wavelength multiplexed (WDM) channels. Each WDM channel can support multiple SONET channels. For example, a WDM channel may contain an OC48 signal, which is equivalent to 48 STS-1 signals at the fundamental SONET data rate of 51.84 Mb/s. This physical interconnection network typically has a mesh topology, as illustrated in the network 100 of FIG. 1. Data flowing between a pair of COs may pass through multiple intermediate COs. This is analogous to a passenger remaining on a train that stops at or passes multiple stations before reaching the passenger's destination. A partial SONET channel, a full SONET channel, or a number of SONET channels may be assigned to a data flow between a particular pair of COs. For high traffic connections, a full wavelength channel (or possibly multiple wavelength channels) may be assigned. Switching of SONET and/or WDM signals would be performed at the COs along the connection path.
Rings can be logically superimposed on the physical mesh topology of FIG. 1, so that data can be forced to flow along a set of interlocking rings. For example COs 102, 104, 106, and 108 form a ring A; COs 104, 110, 112, and 106 form a ring B, and COs 110, 114, and 112 form a ring C. For a particular data flow, the working and protection data travel in opposite directions around the ring. Once the a path is chosen for the working data (the working path) associated with a particular data flow, the path for protection data (the protection path) for this data flow is constrained. COs connected to multiple rings act as hubs in allowing data to be transferred from one ring to another. Data passing through the network would pass through multiple interlocking rings. In the example shown in FIG. 1, data would traverse rings A, B, and C in flowing from a source, or origin, CO 102 to a destination CO 114. Of course, data flows are usually bi-directional so that data would also flow from destination node 114 to source node 102.
In the case shown by FIG. 1, the working paths associated with this data flow from source node 102 to destination node 114 would be clockwise around rings A, B, and C, while the protection path would be counterclockwise around the rings. This is shown more clearly by FIG. 2, which is an expansion of Ring A. The working path is from CO 102 to CO 104, while the protection path is from CO 102 to CO 108 to CO 106 to CO 104.
Rings are awkward building blocks that impose unnecessary constraints on the operation of the interoffice network. Protection capacity must be reserved around each ring. Typically, the shorter distance between two COs on a ring is chosen for the working path, and the longer distance is chosen for the protection path. Consequently, the capacity reserved for protection is usually greater than the working capacity. Also, the ring structure limits provisioning flexibility so that network capacity may be “stranded,” i.e., some capacity will be rendered unusable by protection constraints. For example, consider the case illustrated by FIG. 2. Suppose there is unused capacity on a link between CO 102 and CO 104. This capacity can be assigned to the traffic flow between these two COs only if sufficient capacity is available to be assigned along all the links for protection path from CO 102 to CO 108 to CO 106 to CO 104. If capacity is not available somewhere along this protection path, the excess capacity on the link 103 between CO 102 and CO 104 is stranded.
Establishing protection on a ring-by-ring basis limits restoration capabilities in the face of node failures and multiple failures. A failure at a hub CO might prevent data from being transferred from one ring to another. For example, a failure at CO 104 in FIG. 2 may prevent data from being handed off between rings A and B (FIG. 1), which would interrupt the data flow between the source and destination COs. Also, two failures on a ring could disable both the working and protection paths and prevent data from passing through the ring. For example, failures of link 103 between CO 1 and CO 2 and link 109 between CO 102 and CO 108 (FIG. 2) would disable the data flow between the source and destination nodes (FIG. 1). It is therefore desirable to provide methods for more efficiently configuring networks and transmitting data over the network, while maintaining the desired reliability.